package sort;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:周次煜
 * Date: 2024-04-14
 * Time：14:19
 */
public class MySort {
     /**
      * 插入排序
      * 先放置在 i 之后成立的数进行移位
      * 然后插入最后不成立的数和成立的数中间
      * 时间复杂度： O(n^2)
      * 空间复杂度： O(1)
      * 稳定性： 稳定
      * @param array
      */

    // 插入排序
     public static void insertSort(int[]array) {
          int j=0,tmp=0;
          for (int i = 1; i < array.length; i++) {
               j=i-1;
               tmp=array[i];
               for (; j >= 0 ; j--) {
                    if (array[j] < tmp) {
                         array[j+1]=array[j];
                    } else {
                         break;
                    }
               }

               array[j+1]=tmp;
          }
     }

     /**
      * 插入排序的优化版：
      * 希尔排序
      * 先分组，后插入排序
      * 组数为 j的跳跃跨度
      * 时间复杂度：O（N^1.3）
      * 空间复杂度：O(1)
      * 稳定性：不稳定
      */

     public static void shellSort( int[] array) {
          int gap=array.length;
          while (gap >= 1) {
               gap /= 2;
               shellFunc(array,gap);
          }
     }

     private static void shellFunc(int[]array ,int gap) {
          int j=0,tmp=0;
          for (int i = gap; i < array.length; i++) {
               j=i-gap;
               tmp=array[i];
               for (; j >=0 ; j -= gap) {
                    if (array[j]>tmp) {
                         array[j+gap]=array[j];
                    } else {
                         break;
                    }
               }
               array[j+gap]=tmp;
          }
     }

     /**
      * 选择排序
      * 在其后面筛选最大或最小值的小标进行替换
      * 无论数字是否有序,时间复杂度都一样
      * 时间复杂度 ： O(N^2)
      * 空间复杂度 ：O(1)
      * 稳定性： 不稳定
      */


     public static void selectSort(int [] array) {
          int minIndex=0;
          int j=0;
          for (int i = 0; i < array.length-1; i++) {
               minIndex=i;
               j=i+1;
               for (; j < array.length ; j++) {
                    if (array[j] < array[minIndex]) {
                         minIndex=j;
                    }
               }
               swap(array,minIndex,i);
          }
     }


     /**
      * 插入排序2
      * 利用左边是最小值的小标
      * 右边是最大值的下标
      * 注意一点:交换最小值有可能会影响最大值的交换
      * 需要判断
      * 时间复杂度:O(n^2)
      * 空间复杂度:O(1)
      * 稳定性: 不稳定
      * @param array 待排序数组
      */

     public  static  void selectSort2(int []array) {
          int left=0;
          int right=array.length-1;
          int j=0,maxIndex=0,minIndex=0;
          while (left < right) {
               minIndex=left;
               maxIndex=right;
               for ( j = left; j <= right; j++) {
                    if (array[j]<array[minIndex]) {
                         minIndex=j;
                    }

                    if (array[j]>array[maxIndex]) {
                         maxIndex=j;
                    }
               }

               swap(array,left,minIndex);
               if (maxIndex==left) {
                    maxIndex= minIndex;
               }

               swap(array,right,maxIndex);
               left++;
               right--;
          }
     }
     /**
      * 交换的四种方式
      * @param array ： 需要交换的数组
      * @param x ： 左边个小标
      * @param y： 右边下标
      */

     private static void swap(int[]array,int x,int y) {

          // 双变量赋值
          int a=array[x];
        int b=array[y];

          array[x]=b;
          array[y]=a;

//          a = a ^ b;  // a^b=0
//          b = a ^ b;  // --> a^b^b =a  0^a=a
//          a = a ^ b;  // --> a^b^a =b  0^a=a;


          /**
           * 错误的交换方法
           * 不可用下标引用交换
           * 若下标相同
           * 下标引用时值两个值都会改变
           */

//          array[x]=array[x]^array[y];
//          array[y]=array[x]^array[y];
//          array[x]=array[x]^array[y];



          // 和差交换
//          a = a + b;
//          b = a - b;
//          a = a - b;
//


          // 常规交换
//          int tmp=array[x];
//          array[x]=array[y];
//          array[y]=tmp;
     }

     /**
      * 堆排序 : 利用 大根堆的队头元素 是最大的 插入至最后
      *  将其放在最后面,再重新制造大根堆
      *  时间复杂度: O(N*long(N))
      *  空间复杂度: O(1)
      *  稳定性: 不稳定
      */

     public static void heapSort(int[] array ) {
          int parent = (array.length-2)/2;
          for (;  parent >= 0 ;parent--) {
               createHeap(array,parent);
          }
          for (int i = array.length-1; i >= 0 ; i--) {
               heapFunc(array,i);
          }
     }


     private  static void createHeap(int[]array,int parent) {
          int child= (parent*2)+1;
          while (child < array.length) {

               if (child+1 < array.length && array[child]<array[child+1]) {
                    child++;
               }

               if (array[child]>array[parent]) {
                    swap(array,child,parent);

               } else {
                   break;
               }

               parent = child;
               child = parent*2+1;
          }
     }

     private static void heapFunc(int[]array,int index) {
          swap(array,0,index);
          index--;
          int parent = 0;
          int child = parent*2+1;
          while (child <= index) {
               if (child+1 <= index && array[child] < array[child+1]) {
                    child++;
               }
               if (array[child] >array[parent]) {
                    swap(array,child,parent);
               } else {
                    break;
               }
               parent=child;
               child=parent*2+1;
          }
     }


     /**
      * 冒泡排序
      * 利用把每一个元素都旁边元素进行交换 得出依次大小的排序
      * 时间复杂度: O(N^2)
      * 空间复杂度: O(1)
      * 稳定性: 稳定
      */

     public  static void  bubbleSort(int[]array) {
          boolean b=true;
          for (int i = 0; i < array.length-1; i++) {

               for (int j = 0; j < array.length-1-i; j++) {
                    if (array[j] > array[j+1]) {
                         swap(array,j,j+1);
                         b=false;
                    }
               }

               if (b) {
                    break;
               }
          }
     }

}
